Signal processing the term interpolation
indicates a procedure whereby we move from a discrete time signal
to a continuous time signal. One way to look at the problem is
that we're starting with the sequence of samples. And what we're doing is we are going
to associate a time interval in seconds between samples and
then we're going to somehow fill the gaps that are left
in the space between samples. There are many ways we can do that. So for instance assume we have this
portion of a discrete time signal, one potential interpolation could be this. Now this is not really satisfying because
it seems to ignore most of the data, starts from the first point,
ends at the last point. But what happens in between doesn't seem
to really reflect the nature of the data. Another type of interpolation
could be this line. Now this line does go
through the data points, but it seems to be wandering around too much. There is really an excess of wiggle
in the line that connects the dots. Now let's look at this. This seems to be all right, it goes
through the data points, it seems to be moving smoothly from data point to data
point, it is intuitively satisfying. So let's try to formalize
the things that make this kind of interpolation acceptable. While we interpolate from discrete time
to continuous time, we have to decide on interpolation interval that will be
the time in seconds between samples. And then we build a function of a real
valued variable T making sure that the function goes through
the discrete data points. Namely at all multiples of
the interpolation interval Ts, we make sure that the function goes through
the corresponding discrete data point. The final requirement is that
the function x of t is smooth. Now why is that a reasonable requirement? Well, if you had a function that jumped
vertically between two distinct values, or in other words, if you had a
first-order discontinuity in the function, that would require the underlying
phenomenon to change state in zero time. That would require an internal movement
that is faster than light, and clearly that is physically impossible. The same holds for
second order discontinuities. For instance a function that goes
like this with a sharp corner would require infinite acceleration in
the underlying phenomenon to be able to change direction
instantly like so. The bottom line is that the interpolation
function should be infinitely differentiable because that's the only
thing that guarantees that the underlying physical phenomenon is plausible. A natural solution to obtain an infinitely
differentiable interpolator is to use polynomial interpolation because
polynomials are infinitely differentiable functions. So suppose we have a set of
capital N discrete time points. We know we can build a polynomial of
degree capital N- 1 that goes through the data points. We can write the polynomial in
standard form like this, and to find the values of the coefficients,
we can use the naive approach which consists in setting up
a system of capital N equations. Where we set the value of the polynomial
at all multiples of the interpolation interval Ts as equal to
the corresponding discrete data point. We solve this system of equations and
we find the coefficients. Now let's simplify the notation
a bit without losing any generality in the derivation. We will consider a symmetric interval for
the discrete time signal, so a finite length discrete
time signal defined for n that goes from minus capital
N all the way to capital N. So we have 2N + 1 discrete data points,
and we want to find the interpolation
that goes through this 2N + 1 point. We will also set Ts equal to
1 to lighten the notation, at which point the system of 2N
+ 1 equations looks like so. We have all the values of the polynomial
at multiples of Ts equal to 1 so p- N p- N + 1 all the way
to p of N equal to the corresponding point in
the finite length signal. Now we can solve the system
of equation like this, but this is not really the smartest
way to solve this kind of problem, a better way is to use
LaGrange interpolation. And this is another instance in which
the power of vector spaces comes to our rescue. So remember, we're trying to
find a polynomial of degree 2N. So if we consider pN the space
of all polynomials of degree 2N over the interval minus nN, we can find our polynomials
as a member of this space. And if we find a good basis for
the space, our polynomial will be found easily as a linear
combination of this basis elements. For this kind of approximation problem,
the best basis for the space of finite degree
polynomials is the Lagrange basis. In PN where the degree of the polynomials
is 2N, there are 2N + 1 basis vectors, of course, because a polynomial of
degree 2N is uniquely identified by 2N + 1 coefficients, and
each basis vector has the following form. Now the notation is
maybe a bit complicated. So let's break it down. We have L which indicates
the basis vector, the superscript capital N indicates
the cardinality the basis which is 2N + 1, and the subscript small n indicates
the ordinality of the basis vector in the basis, where it comes in
the order sequence of basis vectors. And once we have this two elements, we can build that element vector
as the product of two capital N monomials of the form t- k
over small n- k where k ranges from minus big N to big N
skipping the value of the index. So we can write them out for
say N equal to 2 so that 2N + 1 is equal to 5 and
we will have five basis vectors. The analytical form is not so
interesting, but we can plug them, let's see how they look. So this would be the first basis vector. This would be the second basis vector. The third basis factor,
the fourth, and the fifth, and all polynomials have degree four. Now if we go back, you will see that
each polynomial has this property, it is equal to 1 for t equal to small n,
so this is L of minus 2. So for t equal to minus 2 the polynomial
is equal to 1, and then for all other integer values of the argument
t, the polynomial is equal to zero. The next one is exactly the same. So for minus 1,
the polynomial is equal to 1, and then for all other integer values
will be equal to zero. The fact that all polynomials
are equal to zero for integer values of the argument except in
one point in which they're equal to 1, is called interpolation
property of the Lagrange basis. And thanks to this property the global
interpolator through the 2N plus 1 data points is given simply by
a linear combination of the Lagrange basis vectors where the weights
are simply the data points themselves. So it's extremely easy to find
the global polynomial interpolator, the proof that the interpolator is the one
that we're looking for is very simple. A polynomial of degree 2N is uniquely
identified by 2N plus 1 points. Now, we have a polynomial now that
goes through the 2N plus 1 data points because of the interpolation
property of the Lagrangian basis vectors. Let's see how this works in practice. So assume we have this five data points. So big N is equal to 2. What we do is we place each one of
the five Lagrange basis vectors in place weighted by
the corresponding data points. So the first Lagrange basis
vector will be this one. We'll go through this data point and will be zero at all other multiples of Ts. The second basis vector is this one and
we'll go through this data point. The third will be this one ,the
fourth will be this one, and the fifth will be this one. Now we sum them all together, and what we have is the polynomial
interpolator which will be the smoothest possible interpolator given
this set of five data points. Now, this is really what
we were looking for. We have a maximally smooth interpolator
for a finite set of points. But the problem is that the interpolation
machine is highly dependent on the size of the data set. If we change the number of points that
we have to interpolate, we have to use a completely different set of basis
vectors that we have to recompute. So while this might work for
small finite data sets, it is clearly impractical if the size
of our data set grows large and in any but
the simplest signal processing application the number of data points would be very,
very large. So what can we do? Well, these were the requirements
that we started with. We certainly have to decide
on an interpolation interval. We certainly have to respect
the data points, and so the interpolator will
have to go through them. The only thing that we can relax
is the smoothness requirement.